4.3 KB · ⇊ 2 parts · ⤓ Micron 4.3 KB · ⤓ HTML 25.7 KB

top

Das chromatische Polynom χ χ ( G , λ λ ) {\displaystyle \chi (G,\lambda )} gibt zu einem Graphen G {\displaystyle G} die Anzahl der möglichen Knotenfärbungen mit λ λ {\displaystyle \lambda } Farben an, d. h. die Anzahl der Färbungen aller Knoten des Graphen, so dass Knoten, die durch eine Kante verbunden sind, verschiedene Farben tragen.

• Beispiele

• Eigenschaften

• Literatur

• Weblinks

Das chromatische Polynom eines Graphen mit n {\displaystyle n} isolierten Knoten ist χ χ ( G , λ λ ) = λ λ n {\displaystyle \chi (G,\lambda )=\lambda ^{n}} . Jeder der n {\displaystyle n} Knoten kann unabhängig von den anderen eine der λ λ {\displaystyle \lambda } Farben annehmen.

Das chromatische Polynom eines vollständigen Graphen K n {\displaystyle K_{n}} ist

χ χ ( K n , λ λ ) = ∏ ∏ i = 0 n − − 1 ( λ λ − − i ) = λ λ ( λ λ − − 1 ) ⋯ ⋯ ( λ λ − − n + 1 ) {\displaystyle \chi (K_{n},\lambda )=\prod _{i=0}^{n-1}(\lambda -i)=\lambda (\lambda -1)\cdots (\lambda -n+1)}

Die Farbe des ersten Knotens kann immer beliebig gewählt werden und für die Färbung des ( i + 1 ) {\displaystyle (i+1)} -ten Knotens sind dann noch λ λ − − i {\displaystyle \lambda -i} Farben übrig.

Für jeden Graphen gibt es eine Zahl χ χ ( G ) {\displaystyle \chi (G)} , sodass χ χ ( G , λ λ ) = 0 {\displaystyle \chi (G,\lambda )=0} für alle λ λ < χ χ ( G ) {\displaystyle \lambda <\chi (G)} . Diese Zahl ist die chromatische Zahl des Graphen und gibt an, wie viele Farben für eine zulässige Knotenfärbung mindestens benötigt werden.

Es ist zunächst einmal nicht klar, dass χ χ {\displaystyle \chi } überhaupt ein Polynom in λ λ {\displaystyle \lambda } ist, dies lässt sich jedoch induktiv zeigen, da für alle Kanten e ∈ ∈ E {\displaystyle e\in E} gilt: χ χ ( G , λ λ ) = χ χ ( G ∖ ∖ { e } , λ λ ) − − χ χ ( G / e , λ λ ) {\displaystyle \chi (G,\lambda )=\chi (G\setminus \{e\},\lambda )-\chi (G/e,\lambda )} (wobei G / e {\displaystyle G/e} derjenige Graph ist, der durch Kantenkontraktion von e entsteht).

• Martin Aigner: Combinatorial theory. Springer, 1979, ISBN 0-387-90376-3.

• M. Swamy, K. Thulasiraman: Graphs, Networks and Algorithms. Krieger Pub., 1980, ISBN 0-471-03503-3.

• William Thomas Tutte: Graph Theory. Addison-Wesley, 1984, ISBN 0-201-13520-5.

• Herbert Wilf: Algorithms and Complexity. Prentice-Hall, 1986, ISBN 0-13-022054-X.

• R. Graham, M. Grötschel , L. László (Hrsg.): Handbook of Combinatorics. Vol. 1, Elsevier, 1995, ISBN 0-262-07170-3.

Wikiversity: Eine Vorlesung über das chromatische Polynom im Rahmen eines Kurses zur diskreten Mathematik

– Kursmaterialien

• Eric W. Weisstein: Chromatic Polynomial. In: MathWorld (englisch).